import java.util.*;

public class Solution {

    //
    public String modifyString(String _s) {
        char[] s = _s.toCharArray();
        int n = s.length;

        for(int i = 0; i < n; i++){
            if(s[i] == '?'){
                for(char ch = 'a'; ch <= 'z'; ch++){
                    if((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)){
                        s[i] = ch;
                    }
                }
            }
        }
        return new String(s);
    }

    //
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret = 0;
        for(int i = 1; i < timeSeries.length; i++){
            int t = timeSeries[i - 1] + duration;
            if(t <= timeSeries[i]){
                ret += duration;
            }else{
                ret += timeSeries[i] - timeSeries[i - 1];
            }
        }
        return ret + duration;
    }

    //
    public String convert(String _s, int numRows) {
        if(numRows == 1) { return _s;}
        StringBuilder s = new StringBuilder();
        int n = _s.length();
        int d = numRows * 2 - 2;
        for (int i = 0; i < n; i += d) {
            s.append(_s.charAt(i));
        }
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - i; i < n || j < n; i += d, j += d) {
                if (i < n) {
                    s.append(_s.charAt(i));
                }
                if (j < n) {
                    s.append(_s.charAt(j));
                }
            }
        }
        for (int i = numRows - 1; i < n; i += d) {
            s.append(_s.charAt(i));
        }
        return s.toString();
    }

    //
    public String countAndSay(int n) {
        String t = "1";

        for(int i = 1; i < n; i++){
            StringBuffer buf = new StringBuffer();
            for(int left = 0, right = 0; right < t.length(); ){
                while(right < t.length() && t.charAt(left) == t.charAt(right)){
                    right++;
                }
                buf.append(Integer.toString(right - left));
                buf.append(t.charAt(left));
                left = right;
            }
            t = buf.toString();
        }
        return t;
    }

    //
    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] s = croakOfFrogs.toCharArray();
        String t = "croak";
        int n = t.length();
        int[] hash = new int[n];

        Map<Character, Integer> index = new HashMap<>();
        for(int i = 0; i < n; i++){
            index.put(t.charAt(i), i);
        }

        for(char ch : s){
            if(ch == t.charAt(0)){
                if(hash[n - 1] != 0){
                    hash[n - 1]--;
                }
                hash[0]++;
            }else{
                int i = index.get(ch);
                if(hash[i - 1] == 0){
                    return -1;
                }else{
                    hash[i - 1]--;
                    hash[i]++;
                }
            }
        }

        for(int i = 0; i < n - 1; i++){
            if(hash[i] != 0){
                return -1;
            }
        }
        return hash[n - 1];
    }

    //
    public int minDifference (int[] a) {
        Arrays.sort(a);
        long ret = (long)1e16 + 10;
        for(int i = 1; i < a.length; i++){
            ret = Math.min(ret, (long)a[i] - a[i - 1]);
        }
        return (int)ret;
    }

    //
}
